class Solution
{
public:
    long long totalCost(vector<int> &costs, int k, int candidates)
    {
        int n = costs.size();
        long long result = 0;
        if (n > 2 * candidates)
        {
            using WorkerHeap = priority_queue<vector<int>, vector<vector<int>>, greater<vector<int>>>;
            WorkerHeap fore, back;
            for (int i = 0; i < candidates; ++i)
            {
                fore.push({costs[i], i});
                back.push({costs[n - 1 - i], n - 1 - i});
            }
            int forePos = candidates;
            int backPos = n - 1 - candidates;
            while (k > 0 && forePos <= backPos)
            {
                if (fore.top() <= back.top())
                {
                    result += fore.top()[0];
                    costs[fore.top()[1]] = INT_MAX;
                    fore.pop();
                    fore.push({costs[forePos], forePos});
                    ++forePos;
                }
                else
                {
                    result += back.top()[0];
                    costs[back.top()[1]] = INT_MAX;
                    back.pop();
                    back.push({costs[backPos], backPos});
                    --backPos;
                }
                --k;
            }
        }
        sort(costs.begin(), costs.end());
        for (int i = 0; i < k; ++i)
        {
            result += costs[i];
        }
        return result;
    }
};